//给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。 
//
// 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 
//
// 你可以假设 nums1 和 nums2 不会同时为空。 
//
// 
//
// 示例 1: 
//
// nums1 = [1, 3]
//nums2 = [2]
//
//则中位数是 2.0
// 
//
// 示例 2: 
//
// nums1 = [1, 2]
//nums2 = [3, 4]
//
//则中位数是 (2 + 3)/2 = 2.5
// 
// Related Topics 数组 二分查找 分治算法 
// 👍 2892 👎 0

package leetcode.editor.cn;
//Java：寻找两个正序数组的中位数
public class P4MedianOfTwoSortedArrays{
    public static void main(String[] args) {
        Solution solution = new P4MedianOfTwoSortedArrays().new Solution();
       // int []input1=new int[]{2,2,3};
        int []input1=new int[0];
        int[] input2=new int[]{2,3};

        System.out.println(solution.findMedianSortedArrays(input1,input2));
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len1=nums1.length;
            int len2=nums2.length;

            int mid=(len1+len2)/2;

            double tmp[]=new double[mid+1];
            int index=0;
            int i=0;
            int j=0;
            while(index<=mid&&i<len1&&j<len2){
                if(nums1[i]<nums2[j]){
                    tmp[index++]=nums1[i++];
                }else{
                    tmp[index++]=nums2[j++];
                }
            }
            if(i<len1){
                while(index<=mid&&i<len1){
                    tmp[index++]=nums1[i++];
                }
            }

            if(j<len2){
                while (index<=mid&&j<len2){
                    tmp[index++]=nums2[j++];
                }
            }

            if((len1+len2)%2==0){
                if(mid-1>=0)
                    return (tmp[mid-1]+tmp[mid])/2;
            }
            return tmp[mid];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
